<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    树和二叉树 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						树和二叉树
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/14 22:26 下午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E6%A0%91%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树的基本概念</h2>
<h3><a id="%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树的定义</h3>
<p>由0个或多个(n &gt;= 0)结点组成的<strong>有限集合T</strong>，有且仅有一个结点称为根(root)，当<code>n &gt; 1</code>时，其余的结点分为m(m &gt;= 0)个互不相交的有限集合T1, T2, ..., Tm，<strong>每个集合本身也是树</strong>，被称作这个根的子树</p>
<p><strong>注意：</strong> 一棵含有n个结点的k叉树，可能达到的最小深度是<strong>log<sub>k</sub>(n + 1)</strong></p>
<h4><a id="%E6%A0%91%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树的表示法</h4>
<h5><a id="%E5%B5%8C%E5%A5%97%E9%9B%86%E5%90%88%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>嵌套集合表示法</h5>
<p><img src="media/16472679744610/16472683989176.jpg" alt="" /></p>
<h5><a id="%E5%B9%BF%E4%B9%89%E8%A1%A8%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>广义表表示法</h5>
<p><strong>(</strong> A(B <strong>(</strong> E(K, L), F <strong>)</strong>, C(G), D <strong>(</strong> H(M), I, J <strong>)</strong>)<strong>)</strong></p>
<h5><a id="%E7%9B%AE%E5%BD%95%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>目录表示法</h5>
<p><img src="media/16472679744610/16472689395950.jpg" alt="" /></p>
<h5><a id="%E5%9C%86%E5%BD%A2%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>圆形表示法</h5>
<p><img src="media/16472679744610/16472689602425.jpg" alt="" /></p>
<h3><a id="%E7%9B%B8%E5%85%B3%E6%9C%AF%E8%AF%AD" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>相关术语</h3>
<ul>
<li>根：即根结点（没有前驱）</li>
<li>叶子：即终端结点（没有后继）</li>
<li>森林：指m棵不相交的数的集合</li>
<li>有序树：结点各子树从左至右有序</li>
<li>无序树：结点各子树可互换位置</li>
<li>结点：即数的数据元素</li>
<li>双亲：即上层结点（直接前驱）</li>
<li>孩子：即下层结点的<strong>子树的根</strong>（直接后继）</li>
<li>兄弟：即同一双亲下的<strong>同层结点</strong></li>
<li>堂兄弟：即双亲位于同一层的结点（但并非同一双亲）</li>
<li>祖先：即从根到该节点所经分支的<strong>所有结点</strong></li>
<li>子孙：即该结点下层子树中的<strong>任意结点</strong></li>
<li>结点的度：结点挂载的<strong>子树数</strong></li>
<li>层次：<strong>从根到该节点</strong>的层数（根节点算第一层）</li>
<li>终端节点：<strong>度为0</strong>的结点，即叶子</li>
<li>分支节点：<strong>度不为0</strong>的结点（也称为内部节点）</li>
<li>树的度：<strong>所有</strong>结点度中的<strong>最大值</strong></li>
<li>树的深度（或高度）：指所有结点中<strong>最大的层次</strong></li>
</ul>
<h3><a id="%E9%80%BB%E8%BE%91%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>逻辑结构</h3>
<p>一对多（1 : n），有<strong>多个直接后继</strong>（如家谱树、录树等），但只有<strong>一个根节点</strong>，且子树之间互不相交</p>
<h3><a id="%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>存储结构</h3>
<ul>
<li>树是<strong>非线性结构</strong>，但仍有顺序存储、链式存储等方式</li>
</ul>
<h4><a id="%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序存储</h4>
<ul>
<li>树的顺序存储方案可规定为从上至下，从左至右将树的结点依次存入内存</li>
<li><strong>复原困难</strong></li>
<li></li>
</ul>
<h4><a id="%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链式存储</h4>
<ul>
<li>树的链式存储方案可用多重链表，1个前驱指针，n个后继指针</li>
<li><strong>等长结构</strong>太浪费，每个结点的度不一定相同</li>
<li><strong>不等长结构</strong>太复杂，要定义多种结构类型</li>
</ul>
<h3><a id="%E6%A0%91%E7%9A%84%E8%BF%90%E7%AE%97" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树的运算</h3>
<ul>
<li>普通树（即多叉树）若不转化为二叉树，则运算很难实现</li>
<li>二叉树的运算仍然是增、删、改、查、排序等，但这些操作必须建立在<strong>对树节点能够遍历</strong>的基础上</li>
</ul>
<h2><a id="%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉树</h2>
<h3><a id="%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉树的定义</h3>
<p>二叉树是由一个根节点以及两颗互不相交的、分别称为<strong>左子树和右子树的二叉树</strong>组成的数，即二叉树是<strong>度为2</strong>且<strong>有序</strong>的树</p>
<h4><a id="%E9%80%BB%E8%BE%91%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>逻辑结构</h4>
<p>一对二(1 : 2)</p>
<h4><a id="%E5%9F%BA%E6%9C%AC%E7%89%B9%E5%BE%81" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>基本特征</h4>
<ul>
<li>每个结点<strong>最多</strong>只有两棵子树（不存在度大于2的结点）</li>
<li>左子树和右子树次序不能颠倒（有序树）</li>
</ul>
<h4><a id="%E5%9F%BA%E6%9C%AC%E5%BD%A2%E6%80%81" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>基本形态</h4>
<ul>
<li>根(<strong>左</strong>子树,<strong>右</strong>子树)</li>
<li>根(<strong>左</strong>子树)</li>
<li>根(<strong>右</strong>子树)</li>
<li>根</li>
<li>空</li>
</ul>
<p>在只有3个结点的情况下，二叉树有5种基本形态，普通树只有2种基本形态：</p>
<h5><a id="%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉树</h5>
<ul>
<li>根(<strong>左</strong>子树,<strong>右</strong>子树)</li>
<li>根(<strong>左</strong>子树(<strong>左</strong>子树))</li>
<li>根(<strong>左</strong>子树(<strong>右</strong>子树))</li>
<li>根(<strong>右</strong>子树(<strong>左</strong>子树))</li>
<li>根(<strong>右</strong>子树(<strong>右</strong>子树))</li>
</ul>
<h5><a id="%E6%99%AE%E9%80%9A%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>普通树</h5>
<ul>
<li>根(子树, 子树)</li>
<li>根(子树(子树))</li>
</ul>
<h3><a id="%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉树的性质</h3>
<h4><a id="%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>满二叉树</h4>
<p>深度为k且有<strong>2<sup>k</sup> - 1</strong>个结点的二叉树<br />
<img src="media/16472679744610/16473398855762.jpg" alt="" /></p>
<h4><a id="%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>完全二叉树</h4>
<ul>
<li>深度为k的，有n个结点的二叉树，每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应</li>
<li>完全二叉树只可能存在1个非空左子树，不可能存在非空右子树<br />
<img src="media/16472679744610/16473398981048.jpg" alt="" /></li>
</ul>
<p>只有满二叉树和完全二叉树可以实现顺序存储</p>
<h4><a id="%E6%80%A7%E8%B4%A81" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>性质1</h4>
<p>在二叉树的第<code>i</code>层上至多有<strong>2<sup>i-1</sup></strong> 个结点(i &gt;= 1)</p>
<h4><a id="%E6%80%A7%E8%B4%A82" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>性质2</h4>
<p>深度为<code>k</code>的二叉树至多有<strong>2<sup>k</sup> - 1</strong>个结点(k &gt;= 1)</p>
<h4><a id="%E6%80%A7%E8%B4%A83" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>性质3</h4>
<p>对于任意一颗二叉树，若度为2的结点数有<strong>n<sub>2</sub></strong> 个，则叶子数(<strong>n<sub>0</sub></strong>)必定为<strong>n<sub>2</sub> + 1</strong>（即<strong>n<sub>0</sub> = n<sub>2</sub> + 1</strong>）</p>
<p><strong>注释：</strong> 二叉树中总体节点数量为n，n = n<sub>0</sub>+ n<sub>1</sub> + n<sub>2</sub></p>
<ul>
<li>n<sub>0</sub>：度为0的结点总数</li>
<li>n<sub>1</sub>：度为1的结点总数</li>
<li>n<sub>2</sub>：度为2的结点总数</li>
</ul>
<h4><a id="%E6%80%A7%E8%B4%A84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>性质4</h4>
<p>具有n个结点的完全二叉树的深度必为<strong>log<sub>2</sub>n + 1</strong></p>
<h4><a id="%E6%80%A7%E8%B4%A85" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>性质5</h4>
<p>对完全二叉树，若从上至下、从左至右编号，则编号为<strong>i</strong>的结点，其左孩子编号必为<strong>2i</strong>，其右孩子编号必为<strong>2i + 1</strong>，其双亲的编号必为<strong>i / 2向下取整</strong>（i = 1为根除外）</p>
<h4><a id="%E6%80%A7%E8%B4%A86" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>性质6</h4>
<p>采用二叉链表法，结点个数为<strong>n</strong>的二叉树，共有<strong>2n</strong>个指针域，会产生<strong>n - 1</strong>个不空的指针域和<strong>n + 1</strong>个空指针域</p>
<h3><a id="%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二叉树的存储结构</h3>
<h4><a id="%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序存储结构</h4>
<p>按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储</p>
<ul>
<li>浪费空间</li>
<li>插入、删除不便</li>
</ul>
<h5><a id="%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E6%88%96%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>完全二叉树或满二叉树</h5>
<p><img src="media/16472679744610/16473555533871.jpg" alt="" /></p>
<ul>
<li>若是完全二叉树或满二叉树，可以做到唯一复原</li>
<li>下标值为<strong>i</strong>的结点，其左孩子的下标必为<strong>2i</strong>，右孩子的下标必为<strong>2i + 1</strong></li>
</ul>
<h5><a id="%E9%9D%9E%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>非完全二叉树</h5>
<p>转为完全二叉树，在各层空缺处补上“虚结点”，内容为空<br />
<img src="media/16472679744610/16473565767773.jpg" alt="" /></p>
<h4><a id="%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链式存储结构</h4>
<pre class="line-numbers"><code class="language-c">typedef struct node
{
    int data;
    struct node *left_child;
    struct node *right_child;
    
    struct node *parent; //可加入一个指向双亲的指针，以便从下至上访问
} node;
</code></pre>
<h2><a id="%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%E5%92%8C%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历二叉树和线索二叉树</h2>
<h3><a id="%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历二叉树</h3>
<h4><a id="%E9%81%8D%E5%8E%86%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历定义</h4>
<p>按某种搜索路线访问每个结点且<strong>不重复</strong>，约定对每个结点的查看都是“先左后右”</p>
<h4><a id="%E9%81%8D%E5%8E%86%E7%94%A8%E9%80%94" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历用途</h4>
<p>它是树结构插增、删、改、查、排序运算的前提模式二叉树一切运算的<strong>基础和核心</strong></p>
<h4><a id="%E9%81%8D%E5%8E%86%E6%96%B9%E6%A1%88" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历方案</h4>
<p>二叉树由根<code>D</code>、左子树<code>L</code>、右子树<code>R</code>构成<code>D</code>、<code>L</code>、<code>R</code>的组合定义了六种可能的遍历方案：</p>
<ul>
<li><code>LDR</code> 左-根-右</li>
<li><code>LRD</code> 左-右-根</li>
<li><code>DLR</code> 根-左-右</li>
<li><code>DRL</code> 根-右-左</li>
<li><code>RDL</code> 右-根-左</li>
<li><code>RLD</code> 右-左-根</li>
</ul>
<p>若限定先左后右，则有三种实现方案</p>
<ul>
<li>先序遍历：<code>DLR</code> （先访问根结点） 又称波兰式遍历</li>
<li>中序遍历：<code>LDR</code> （中置访问根结点）</li>
<li>后序遍历：<code>LRD</code> （后访问根结点） 又称逆波兰式遍历</li>
</ul>
<p>以下图为例：<br />
<img src="media/16472679744610/16473580274344.jpg" alt="" /><br />
<strong>访问结果：</strong></p>
<table>
<thead>
<tr>
<th>实现方案</th>
<th>结果</th>
</tr>
</thead>
<tbody>
<tr>
<td>先序遍历<code>DLR</code></td>
<td>A B D E C</td>
</tr>
<tr>
<td>中序遍历<code>LDR</code></td>
<td>D B E A C</td>
</tr>
<tr>
<td>后序遍历<code>LRD</code></td>
<td>D E B C A</td>
</tr>
</tbody>
</table>
<h4><a id="%E4%BB%A3%E7%A0%81%E6%BC%94%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>代码演示</h4>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

typedef char TElemType;
//定义树的结点
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *l_child; //指向左子树的地址
    struct BiTNode *r_child; //指向右子树的地址
} BiTNode, *BiTree;

//创建树
void CreateBiTree(BiTree &amp;T);
//先序遍历
void PreOrderTraverse(BiTree T);
//中序遍历
void InOrderTraverse(BiTree T);
//后序遍历
void PostOrderTraverse(BiTree T);

int main()
{
    BiTree T;
    CreateBiTree(T);
    PreOrderTraverse(T);
    printf(&quot;\n&quot;);
    InOrderTraverse(T);
    printf(&quot;\n&quot;);
    PostOrderTraverse(T);
    return 0;
}

//创建树
void CreateBiTree(BiTree &amp;T)
{
    //先序创建（根-左-右）
    char ch;
    ch = getchar();
    if (ch == '#')
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        if (!T)
            return;
        T-&gt;data = ch;
        CreateBiTree(T-&gt;l_child);
        CreateBiTree(T-&gt;r_child);
    }
}
//先序遍历
void PreOrderTraverse(BiTree T)
{
    if (T)
    {
        printf(&quot;%c&quot;, T-&gt;data);
        PreOrderTraverse(T-&gt;l_child);
        PreOrderTraverse(T-&gt;r_child);
    }
}
//中序遍历
void InOrderTraverse(BiTree T)
{
    if (T)
    {
        InOrderTraverse(T-&gt;l_child);
        printf(&quot;%c&quot;, T-&gt;data);
        InOrderTraverse(T-&gt;r_child);
    }
}
//后序遍历
void PostOrderTraverse(BiTree T)
{
    if (T)
    {
        PostOrderTraverse(T-&gt;l_child);
        PostOrderTraverse(T-&gt;r_child);
        printf(&quot;%c&quot;, T-&gt;data);
    }
}
</code></pre>
<p>由以上三种遍历算法可知，从递归的角度看，这三种<strong>算法完全相同</strong>，或者说这三种遍历算法的<strong>访问路径相同</strong>，只是<strong>访问结点的时机不同</strong></p>
<p>访问路径如下图所示，从虚线的出发点到终点的路径上，每个结点都会经过<strong>3次</strong></p>
<ul>
<li>先序遍历：第1次经过时访问结点</li>
<li>中序遍历：第2次经过时访问结点</li>
<li>后序遍历：第3次经过时访问结点</li>
</ul>
<p><img src="media/16472679744610/16473687381320.jpg" alt="" /></p>
<h4><a id="%E8%BF%90%E7%AE%97%E6%95%88%E7%8E%87" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>运算效率</h4>
<p>树深为k的递归遍历需要<code>k + 1</code>个辅助单元</p>
<ul>
<li>时间效率：<strong>O(n)</strong>（取决于结点个数，每个结点只访问一次）</li>
<li>空间效率：<strong>O(n)</strong>（取决于树的深度，栈占用的最大辅助单元）</li>
</ul>
<h4><a id="%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E6%B7%B1%E5%BA%A6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>求二叉树深度</h4>
<p>只查找各节点后继链表指针，若<strong>左（右）孩子</strong>的<strong>左（右）指针</strong>非空，则层次数加1，否则函数返回</p>
<ul>
<li>当T = NULL时，深度为0</li>
<li>否则<strong>T的深度 = MAX{左子树深度, 右子树深度} + 1</strong></li>
</ul>
<pre class="line-numbers"><code class="language-cpp">int TreeDepth(BiTree T)
{
    int hl, hr, max;
    if (T)
    {
        hl = TreeDepth(T-&gt;l_child);
        hr = TreeDepth(T-&gt;r_child);
        max = hl &gt; hr ? hl : hr;
        return max + 1;
    }
    return 0;
}
</code></pre>
<h4><a id="%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%93%E7%82%B9%E6%80%BB%E6%95%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>求二叉树的结点总数</h4>
<pre class="line-numbers"><code class="language-c">int TreeNum(BiTree T)
{
    int l_num, r_num, num;
    if (T)
    {
        l_num = TreeNum(T-&gt;l_child);
        r_num = TreeNum(T-&gt;r_child);
        num = r_num + r_num + 1;
        return num;
    }
    return 0;
}
</code></pre>
<h4><a id="%E5%88%A4%E5%88%AB%E7%BB%99%E5%AE%9A%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%88%E5%8D%B3%E9%A1%BA%E5%BA%8F%E6%A0%91%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>判别给定二叉树是否为完全二叉树（即顺序树）</h4>
<pre class="line-numbers"><code class="language-c">#define TRUE 1
#define FALSE 0

int TreeIdentify(BiTree T)
{
    if (T)
    {
        TreeIdentify(T-&gt;l_child);
        TreeIdentify(T-&gt;r_child);
        if (T-&gt;l_child == NULL &amp;&amp; T-&gt;r_child != NULL)
            return FALSE;
        return TRUE;
    }
    return TRUE;
}
</code></pre>
<h3><a id="%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线索二叉树</h3>
<ul>
<li>普通二叉树只能找到结点的左右孩子信息，而该节点的直接前驱和直接后继只能在遍历过程中获得</li>
<li>若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树</li>
<li>例如中序遍历结果：BDCEAFHG，实际上已经将二叉树转为线性排列，显然具有唯一前驱和唯一后继</li>
</ul>
<p><img src="media/16472679744610/16474240689266.jpg" alt="" /></p>
<h4><a id="%E8%A7%84%E5%AE%9A" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>规定</h4>
<ul>
<li>若结点有左子树，则lchild指向其左孩子，否则，lchild指向其直接前驱（即线索）</li>
<li>若结点有右子树，则rchild指向其右孩子，否则，rchild指向其直接后继（即线索）</li>
<li>为区别两种不同情况，特增加两个标志域：
<ul>
<li>当Tag域为0时，表示正常情况</li>
<li>当Tag域为1时，表示线索情况</li>
</ul>
</li>
</ul>
<h4><a id="%E6%9C%AF%E8%AF%AD" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>术语</h4>
<ul>
<li>线索链表：用<strong>含Tag的结点样式</strong>所构成的二叉链表</li>
<li>线索：指向节点<strong>前驱</strong>和<strong>后继</strong>的<strong>指针</strong></li>
<li>线索二叉树：加上线索的二叉树</li>
<li>线索化：对二叉树以某种次序遍历使其<strong>变为线索二叉树的过程</strong>
<ul>
<li><strong>线索化过程</strong>就是在遍历过程中<strong>修改空指针的过程</strong>：
<ul>
<li>将空的lchild改为结点的直接前驱</li>
<li>将空的rchild改为结点的直接后继</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2><a id="%E6%A0%91%E5%92%8C%E6%A3%AE%E6%9E%97" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树和森林</h2>
<h3><a id="%E6%A0%91%E5%92%8C%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树和二叉树的转换</h3>
<h4><a id="%E8%BD%AC%E6%8D%A2%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>转换步骤</h4>
<ul>
<li>将树中同一结点的兄弟相连</li>
<li>保留结点的最左孩子连线，删除其它孩子连线</li>
<li>将同一孩子的连线绕左孩子旋转45°</li>
</ul>
<p>转换完成之后的<strong>右孩子</strong>均为<strong>原先的兄弟</strong></p>
<h5><a id="%E6%96%B9%E6%B3%95%EF%BC%9A%E5%8A%A0%E7%BA%BF%E6%8A%B9%E7%BA%BF%E6%97%8B%E8%BD%AC" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>方法：加线 - 抹线 - 旋转</h5>
<p><img src="media/16472679744610/16474277942867.jpg" alt="" /></p>
<h4><a id="%E8%BF%98%E5%8E%9F%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>还原步骤</h4>
<ul>
<li>将所有右孩子转换为兄弟</li>
</ul>
<h4><a id="%E7%89%B9%E8%AF%81" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>特证</h4>
<p>转换为二叉树后，二叉树的根结点不具有右孩子</p>
<p><img src="media/16472679744610/16474280206276.jpg" alt="" /></p>
<h3><a id="%E6%A3%AE%E6%9E%97%E5%92%8C%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>森林和二叉树的转换</h3>
<h4><a id="%E6%96%B9%E6%B3%95%E4%B8%80" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>方法一</h4>
<ul>
<li>每颗树先各自转换为二叉树</li>
<li>依次连接到前一个二叉树的右子树上</li>
<li></li>
</ul>
<h4><a id="%E6%96%B9%E6%B3%95%E4%BA%8C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>方法二</h4>
<ul>
<li>森林直接转换为兄弟，再转换为二叉树</li>
</ul>
<p><img src="media/16472679744610/16474283179417.jpg" alt="" /></p>
<h4><a id="%E8%BF%98%E5%8E%9F%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>还原步骤</h4>
<ul>
<li>将二叉树最右侧的右子树还原为单独的树</li>
<li>将其余右子树还原为兄弟</li>
</ul>
<p><img src="media/16472679744610/16474285836024.jpg" alt="" /></p>
<h3><a id="%E6%A0%91%E5%92%8C%E6%A3%AE%E6%9E%97%E7%9A%84%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树和森林的存储方式</h3>
<h4><a id="%E6%A0%91%E7%9A%84%E4%B8%89%E7%A7%8D%E5%B8%B8%E7%94%A8%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>树的三种常用存储方式</h4>
<h5><a id="%E5%8F%8C%E4%BA%B2%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>双亲表示法</h5>
<p>用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置</p>
<ul>
<li>找双亲容易，找后继难</li>
</ul>
<p><img src="media/16472679744610/16474308303105.jpg" alt="" /></p>
<h5><a id="%E5%AD%A9%E5%AD%90%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>孩子表示法</h5>
<p>将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表），再将n个表头用数组存放起来，形成一个混合结构</p>
<ul>
<li>找孩子容易，找前驱难</li>
</ul>
<p><img src="media/16472679744610/16474309205373.jpg" alt="" /></p>
<h5><a id="%E5%AD%A9%E5%AD%90%E5%85%84%E5%BC%9F%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>孩子兄弟表示法</h5>
<p>用二叉链表来表示树，但链表中的两个指针域含义不同，左指针指向该节点的第一个孩子，右指针指向该节点的下一个兄弟结点</p>
<ul>
<li>与二叉树没有区别</li>
</ul>
<p><img src="media/16472679744610/16474311446146.jpg" alt="" /></p>
<h3><a id="%E6%A3%AE%E6%9E%97%E7%9A%84%E9%81%8D%E5%8E%86" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>森林的遍历</h3>
<h4><a id="%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>先序遍历</h4>
<ul>
<li>若森林为空，返回</li>
<li>访问森林中第一棵树的根结点</li>
<li>先序遍历第一棵树中根结点的子树森林</li>
<li>先序遍历除去第一棵树之后剩余的树构成的森林</li>
</ul>
<h4><a id="%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>中序遍历</h4>
<ul>
<li>若森林为空，返回</li>
<li>中序遍历森林中第一棵树的根结点的子树森林</li>
<li>访问第一棵树的根结点</li>
<li>中序遍历除去第一棵树之后剩余的树构成的森林</li>
</ul>
<h2><a id="huffman%E6%A0%91%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Huffman树及其应用</h2>
<h3><a id="%E7%9B%B8%E5%85%B3%E6%A6%82%E5%BF%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>相关概念</h3>
<ul>
<li>路径：由一结点到另一结点间的分支所构成</li>
<li>路径长度：路径上的分支数目（<code>a -&gt; e</code>的长度路径 = 2）</li>
<li>树的路径长度：从树根到每一结点的路径长度之和（树的长度 = 10)</li>
<li>带权路径长度：结点到树根之间的路径长度与该节点上权的乘积</li>
<li>树的带权路径长度：树中所有叶子结点的带权路径长度之和</li>
<li>Huffman树：带权路径长度最小的数</li>
</ul>
<p><img src="media/16472679744610/16474318759679.jpg" alt="" /></p>
<h4><a id="%E5%B8%A6%E6%9D%83%EF%BC%88wpl%EF%BC%89%E8%B7%AF%E5%BE%84%E9%95%BF%E5%BA%A6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>带权（WPL）路径长度</h4>
<p>树中所有叶子结点的带权路径长度之和</p>
<ul>
<li>权值集成在结点上</li>
</ul>
<p><img src="media/16472679744610/16474324892945.jpg" alt="" /></p>
<p><img src="media/16472679744610/16474324411065.jpg" alt="" /></p>
<h3><a id="%E5%9F%BA%E6%9C%AC%E6%80%9D%E6%83%B3" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>基本思想</h3>
<p>权值大的结点用短路径，权值小的结点用长路径</p>
<h3><a id="%E6%9E%84%E9%80%A0huffman%E6%A0%91%E7%9A%84%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>构造Huffman树的步骤</h3>
<ul>
<li>由给定的n个权值 <strong>{w<sub>0</sub>, w<sub>1</sub>, w<sub>2</sub>, ..., w<sub>n-1</sub>}</strong>，构造具有n棵扩充二叉树的森林<strong>F = {T<sub>0</sub>, T<sub>1</sub>, T<sub>2</sub>, ..., T<sub>n-1</sub>, }</strong>，其中每一棵扩充二叉树<strong>T<sub>i</sub></strong> ，只有一个带有权值<strong>w<sub>i</sub></strong> 的根结点，其左、右子树均为空</li>
<li>重复以下步骤，直到F中仅剩下一棵树为止：
<ul>
<li>在F中选取两棵<strong>根结点的权值最小</strong>的扩充二叉树，作为左、右子树构造一棵<strong>新的二叉树</strong>，置新的二叉树的根结点的权值为其<strong>左、右子树上根结点的权值之和</strong></li>
<li>在F中删去这两棵二叉树</li>
<li>把新的二叉树加入F</li>
</ul>
</li>
</ul>
<p><img src="media/16472679744610/16474330725543.jpg" alt="" /></p>
<h4><a id="huffman%E7%BC%96%E7%A0%81%E8%BF%87%E7%A8%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Huffman编码过程</h4>
<ul>
<li>按左0右1对Huffman树的所有分支编号</li>
<li>Huffman编码结果：d = 0, i = 10, a = 110, n = 111</li>
<li>WPL = 1 * 7 + 2 * 5 + 3 * (2 + 4)</li>
<li>任何一个编码都不是另一个编码的前缀，但称为前缀编码</li>
</ul>
<p><img src="media/16472679744610/16474338121876.jpg" alt="" /></p>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>